﻿//#include <iostream>
//using namespace std;
//
//typedef long long LL;
//
//LL a, b, p;
//
//LL qmul(LL a,LL b, LL p)
//{
//	LL ret = 0;
//	while (b)
//	{
//		if (b & 1)
//		{
//			ret += a;
//		}
//		a = a + a;
//		b >>= 1;
//	}
//	return ret;
//}
//
//int main()
//{
//	cin >> a >> b >> p;
//	cout << qmul(a,b,p) << endl;
//
//	return 0;
//}

//离散化模板
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const int N = 1e5;
//
//int n; 
//int a[N];
//
//int pos;
//int disc[N];
//
//int find(int x)
//{
//	int l = 1; int r = pos;
//	while (l < r)
//	{
//		int mid = (l + r) / 2;
//		if (disc[mid] >= x)
//		{
//			r = mid;
//		}
//		else
//		{
//			l = mid + 1;
//		}
//	}
//	return l;
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//		disc[++pos] = a[i];
//	}
//
//	//离散化
//	sort(disc + 1, disc + 1 + pos);
//	pos = unique(disc + 1, disc + 1 + pos) - (disc + 1);
//	for (int i = 1; i <= n; i++)
//	{
//		cout << a[i] << "离散化之后的数据" << find(a[i]) << endl;
//	}
//	return 0;
//}
//输入：
//10
//1999999
//12
//1999999
//- 48444
//568
//12
//- 100
//- 2845630
//100000001
//263
// 输出：
//1999999离散化之后的数据7
//12离散化之后的数据4
//1999999离散化之后的数据7
//- 48444离散化之后的数据2
//568离散化之后的数据6
//12离散化之后的数据4
//- 100离散化之后的数据3
//- 2845630离散化之后的数据1
//100000001离散化之后的数据8
//263离散化之后的数据5


//#include<iostream>
//#include<algorithm>
//#include<unordered_map>
//
//using namespace std;
//
//const int N = 1e5;
//
//int a[N];
//int n;
//
//int disc[N];
//int pos;
//unordered_map<int, int> id;
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//		disc[++pos] = a[i];
//	}
//
//	sort(disc + 1, disc + 1 + pos);
//	int cnt = 0;
//	for (int i = 1 ; i <= n; i++)
//	{
//		int x = disc[i];
//		if (id.count(x))
//		{
//			continue;
//		}
//		++cnt;
//		id[x] = cnt;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		cout << a[i] << "离散化之后的数据" << id[a[i]] << endl;
//	}
//
//	return 0;
//}

//火烧赤壁
//#include <iostream>
//#include <unordered_map>
//#include <algorithm>
//using namespace std;
//const int N = 2e4 + 10;
//int n;
//int a[N], b[N];
//int pos;
//int disc[N * 2];
//unordered_map<int, int> id;
//int f[N * 2];
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i] >> b[i];
//		disc[++pos] = a[i]; disc[++pos] = b[i];
//	}
//	// 离散化 
//	sort(disc + 1, disc + 1 + pos);
//	pos = unique(disc + 1, disc + 1 + pos) - (disc + 1); // 去重 
//	for (int i = 1; i <= pos; i++)
//	{
//		id[disc[i]] = i; // 哈希表只完成保存最终结果的⼯作 
//	}
//	// 在离散化的基础上，做差分 
//	for (int i = 1; i <= n; i++)
//	{
//		int l = id[a[i]], r = id[b[i]];
//		f[l]++; f[r]--;
//	}
//	// 还原数组 
//	for (int i = 1; i <= pos; i++) f[i] += f[i - 1];
//	// 统计结果 
//	int ret = 0;
//	for (int i = 1; i <= pos; i++)
//	{
//		int j = i;
//		while (j <= pos && f[j] > 0) j++;
//		// 累加上原始的⻓度 
//		ret += disc[j] - disc[i];
//		i = j;
//	}
//	cout << ret << endl;
//	return 0;
//}
